In wireless communications or the like, a CRC computation has been widely used to detect the presence or absence of a transmission error on the receiving side (refer to, for example, Japanese Patent Laid-open No. 2003-134092).
In a communication system that performs the CRC computation, a transmitting device generates a CRC code, based on information data to be transmitted and transmits the information data (transmit data) connected with the CRC code. On the other hand, a receiving device performs a CRC computation, based on received data in parallel with the fetching of received data excluding the CRC code from the received data (receive data) to thereby detect the presence or absence of a transmission error.
The CRC computation will be described below in further detail. First, m-bit information data is defined as an m−1 order polynomial A(x)=am-1xm-1+am-2xm-2+ . . . +a1x1+a0x0 using elements am-1, am-2, . . . , a1, a0 of a Galois field GF(2) defined modulo 2. A remainder of order n−1 obtained by dividing xnA(x) by a generating or generator polynomial G(x) of order n is defined as R(x)=rn-1xn-1+rn-2xn-2+ . . . +r1x1+r0x0. In this case, a relationship of XnA(x)=Q(x)G(x)+R(x) is established. Here, Q(x) is a polynomial equivalent to the quotient of division at an integral number. A bit string expressed in the elements rn-1, rn-2, . . . , r1, r0 is generally called CRC code. The computation of determining the CRC code is generally called “CRC computation”.
In the above xnA(x)=Q(x)G(x)+R(x), symbol + means an addition by a Galois field defined modulo 2 and is equivalent to exclusive Oring, i.e., XORing as viewed from a bit string. Thus, data expressed in the sign of the left side xnA(x)+R(x) at the time that xnA(x)+R(x) is expressed as equal to Q(x)G(x), i.e., xnA(x)+R(x)=Q(x)G(x), that is, the data being expressed in am-1, am-2, . . . , a1, a0, rn-1, rn-2, . . . , r1, r0 is transmitted upon data transfer. This data is assumed to be B(x) below.
When (m,n)=(10,5), A(x)=x9+x7+x3+x2+x0, and G(x)=x5+x4+x2+x0 as shown in FIG. 17 by way of example, R(x)=x3+x2+x1 is established and hence transmit data results in B(x)=x14+x12+x8+x7+x5+x3+x2+x1.
On the receiving side, receive data is assumed to be xnA(x)+R(x) and a remainder at G(x) is determined as a CRC check result. If no error exists upon the data transfer, then xnA(x)+R(x) is equal to Q(x)G(x) and hence the CRC check result becomes 0. On the other hand, when an error E(x) occurs upon the data transfer, the receive data can be expressed in the form of xnA(x)+R(x)+E(x) and hence the CRC check result does not reach 0.
As the conventional communication system that performs the CRC computation, there is known one wherein error detection dedicated to a frame header and error detection (FCS (frame check sequence)) for the whole reception frame are effected on each of reception frames on the receiving side, and wherein the individual reception frames are further brought into blocks and the result of calculation of a remainder based on a cyclic redundancy code set for each block is used in PCS, thereby attaining multiplexing of error detection and improving the accuracy of error detection (refer to, for example, Japanese Patent Laid-Open No. 2002-335229).
In the conventional communication system, R(x)=0 and B(x)=0 as shown in FIG. 18 where information data indicative of all 0 is transferred, i.e., A(x)=0. Thus, a problem arises in that in a system in which the frequencies on the transmitting and receiving sides are different from each other, an error cannot be detected even though one bit-shifted data is received, and the data is misjudged as proper data. This problem may take place where when, for example, CDR (Clock and Data Recovery) is used in a reception system, the frequency of a clock recovered by the CDR drifts as compared with the transmitting side.
When the error E(x) is divided by G(x), that is, when E(x) can be expressed in the form of E(x)=S(x)G(x) using an arbitrary polynomial S(x), receive data containing the error E(x) is expressed in the form of xnA(x)+R(x)+E(x)=Q(x)G(x)+S(x)G(x)=(Q(x)+S(x))G(x). Thus, a problem arises in that since a remainder at G(x) becomes 0 as shown in FIG. 19, an error cannot be detected and the receive data is misjudged as proper data.